package org.example.Sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
/**
 * <pre>
 *     name 桶排序
 *     time NLog（N）
 *     space NLog(N)
 * </pre>
 * */
public class BucketSort {
    /**
     * @apiNote var关键字 Java10引入的动态类型，通过赋初值推断类型
     * */
    public void sort(int[] arr){
        int regex =10;
        var list = new ArrayList[regex];



        double math = 1;
        int count=0;

        while (count<arr.length) {
            int index = 0;
            //初始化桶
            for (int i = 0; i < list.length; i++) {
                list[i] = new ArrayList<Integer>();
            }
            //
            for (int i : arr) {
                index =  (int) (i / Math.pow(regex, math))% regex;
                if(index==0)count++;
                list[index].add(i);
            }
            index = 0;
            for (var ls:list) {
                if(ls.size()>0){
                    for (var l : ls) {
                        arr[index++] =(Integer) l;
                    }
                }
            }
            math++;
        }
    }

    public static void main(String[] args) {
        int arr[] = {10,111,10,1101,11};
        new BucketSort().sort(arr);
        Arrays.stream(arr).forEach(System.out::println);
    }
}
